package com.zp.self.module.level_4_算法练习.数据结构.数组;

import java.util.ArrayList;
import java.util.List;

/**
 * @author By ZengPeng
 */
public class 力扣_56_合并区间 {
    //测试
    public static void main(String[] args) {
        int[][] merge;
        merge = new 力扣_56_合并区间().merge(new int[][]{{1, 3}, {8, 10}, {2, 6}, {15, 18}});
        for (int[] aMerge : merge) System.out.print("[" + aMerge[0] + "," + aMerge[1]+"],");

        System.out.println();
        merge = new 力扣_56_合并区间().merge(new int[][]{{1,4},{2,3}});
        for (int[] aMerge : merge) System.out.print("[" + aMerge[0] + "," + aMerge[1]+"],");

    }

    /**
    题目：以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
          请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

     示例 1：
     输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
     输出：[[1,6],[8,10],[15,18]]
     解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

     示例 2：
     输入：intervals = [[1,4],[4,5]]
     输出：[[1,5]]
     解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

    分析：【perfect】确认是否有交集，而且要确保上下区间有序？还是保留区间遍历？
       1.位图：10000个点，标记true,最后重新组装 【太慢了】
       2.排序 【根据大小合并】    执行用时：8 ms, 在所有 Java 提交中击败了38.13%的用户
            优化：字写快速排序   执行用时：3 ms, 在所有 Java 提交中击败了98.97%的用户

    边界值 & 注意点：
       1.
     **/
    public int[][] merge(int[][] intervals) {
        //系统的快速排序
//        Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[0]));

        //手写快速排序
        myQuickSort(intervals,0,intervals.length-1);

        //简单选择排序
  /* int[] mid;
        for (int i = 0; i < intervals.length; i++) {
            for (int j = i; j < intervals.length; j++) {
                if(intervals[i][0]>intervals[j][0]){
                    mid = intervals[i];
                    intervals[i] = intervals[j];
                    intervals[j] = mid ;
                }
            }
        }*/

        //合并
        int start =  intervals[0][0],end =  intervals[0][1];
        List<int[]> list = new ArrayList<>();
        for (int i = 1; i < intervals.length; i++) {
            if(intervals[i][0]<=end) {
                end = Math.max(end,intervals[i][1]);// 交集，或者被包含
            }else {
                list.add(new int[]{start,end});
                start = intervals[i][0];
                end =  intervals[i][1];
            }
        }
        list.add(new int[]{start,end});
        return  list.toArray(new int[list.size()][]);
    }


    private void myQuickSort(int[][] arr, int left, int right) {
        if(left>right) return;
        int nLeft = left,nRight=right;
        int referPoint = arr[left][0];
        int[] referPointArr = arr[left];
        while (nLeft!=nRight){
            //这里arr[nRight]==referPoint 为什么要跳过？ 因为：等于分叉值的放在左边，下一次左区域递归会移到最右边的. 右边的同理。
            while (arr[nRight][0]>=referPoint && nRight>nLeft)//【从右】不断right--,找arr[right] < P的值放到L[空],此时arr[right]就空出来了
                nRight--;
            //这里要找到了才会替换吧？ 非也 ：当nRight == nLeft 时，跳出也交换一次不会出问题。
            arr[nLeft] = arr[nRight];

            while (arr[nLeft][0]<=referPoint && nRight>nLeft)//【从左】不断left++,找arr[left] < P的值放到arr[right],此时arr[left]就空出来了
                nLeft++;
            arr[nRight] = arr[nLeft];
        }
        arr[nLeft] = referPointArr;
        myQuickSort(arr,left,nLeft-1);//nLeft这个节点就拍好顺序了
        myQuickSort(arr,nLeft+1,right);
    }
}
